package com.shm.leetcode;

/**
 * 367. 有效的完全平方数
 * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
 *
 * 进阶：不要 使用任何内置的库函数，如  sqrt 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：num = 16
 * 输出：true
 * 示例 2：
 *
 * 输入：num = 14
 * 输出：false
 *
 *
 * 提示：
 *
 * 1 <= num <= 2^31 - 1
 * @author SHM
 */
public class IsPerfectSquare {
    /**
     * 方法二：暴力
     * 思路和算法
     *
     * 如果 \textit{num}num 为完全平方数，那么一定存在正整数 xx 满足 x \times x = \textit{num}x×x=num。于是我们可以从 11 开始，从小到大遍历所有正整数，寻找是否存在满足 x \times x = \textit{num}x×x=num 的正整数 xx。在遍历中，如果出现正整数 xx 使 x \times x > \textit{num}x×x>num，那么更大的正整数也不可能满足 x \times x = \textit{num}x×x=num，不需要继续遍历了。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(\sqrt{n})O(
     * n
     * ​
     *  )，其中 nn 为正整数 \textit{num}num 的最大值。我们最多需要遍历 \sqrt{n} + 1
     * n
     * ​
     *  +1 个正整数。
     *
     * 空间复杂度：O(1)O(1)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/valid-perfect-square/solution/you-xiao-de-wan-quan-ping-fang-shu-by-le-wkee/
     * @param num
     * @return
     */
    public boolean isPerfectSquare(int num) {
        //long
        long x = 1,area = 1;
        while (area<=num){
            if (area==num){
                return true;
            }
            x++;
            area=x*x;
        }
        return false;
    }

    /**
     *
     * @param num
     * 方法三：二分查找
     * 思路和算法
     *
     * 考虑使用二分查找来优化方法二中的搜索过程。因为 \textit{num}num 是正整数，所以若正整数 xx 满足 x \times x = \textit{num}x×x=num，则 xx 一定满足 1 \le x \le \textit{num}1≤x≤num。于是我们可以将 11 和 \textit{num}num 作为二分查找搜索区间的初始边界。
     *
     * 细节
     *
     * 因为我们在移动左侧边界 \textit{left}left 和右侧边界 \textit{right}right 时，新的搜索区间都不会包含被检查的下标 \textit{mid}mid，所以搜索区间的边界始终是我们没有检查过的。因此，当\textit{left} = \textit{right}left=right 时，我们仍需要检查 \textit{mid} = (\textit{left}+\textit{right}) / 2mid=(left+right)/2。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(\log n)O(logn)，其中 nn 为正整数 \textit{num}num 的最大值。
     *
     * 空间复杂度：O(1)O(1)。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/valid-perfect-square/solution/you-xiao-de-wan-quan-ping-fang-shu-by-le-wkee/
     */
    public boolean isPerfectSquare_1(int num) {
        int left=0,right=num;
        while (left<=right){
            int mid = (right-left)/2+left;
            //long
            long area = (long) mid *mid;
            if (area<num){
                left=mid+1;
            }else if (area>num){
                right=mid-1;
            }else {
                return true;
            }
        }
        return false;
    }
}
